#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:
    def strStr(self, source, target):
        if source is None or target is None:
            return -1

        if target == '':
            return 0

        new_s = target + '$' + source       # 中间加'$'异常重要, '$'一定不能和source[0]相同. 防止本来应该匹配len(target)字符的, 结果多匹配
        # print(new_s)
        return self.z_algo(new_s, len(target))

    def z_algo(self, s, pattern_len):
        self.s = s
        self.l = len(self.s)
        ret =  self.z_calc(pattern_len)
        # print(self.z_table)
        return ret

    def z_calc(self, pattern_len):
        self.z_table = self.l * [0]
        left = 1

        while left < self.l:
            matched_cnt = self._match_from(left)
            self.z_table[left] = matched_cnt

            # matched
            if matched_cnt == pattern_len and left >= pattern_len:
                return left - pattern_len - 1

            if matched_cnt in [0, 1]:
                # 生成[L, R)
                left += 1
            else:
                # 根据[L, R) 快速往后处理
                right = left + matched_cnt              # [left, right)

                update_to, matched_left = self._try_update_after(left, right, pattern_len)
                if matched_left != -1:
                    return matched_left - pattern_len - 1

                left = update_to

        return -1

    def _match_from(self, z_from, origin_from=0):
        origin_to = origin_from
        z_to = z_from

        while z_to < self.l:
            if self.s[origin_to] != self.s[z_to]:
                break
            origin_to += 1
            z_to += 1

        # return last not match
        return z_to - z_from

    def _try_update_after(self, left, right, pattern_len):
        # return right作为上层最新left
        # [left, right)
        assert right <= self.l
        cur_match_cnt = self.z_table[left]
        assert right - left == cur_match_cnt

        cur_idx = left + 1
        while cur_idx < right:
            # cur_idx = left + i
            offset = cur_idx - left
            match_to = cur_idx + self.z_table[offset]       # [left+i, match_to) 开闭区间
            # print('cur_idx %s' % cur_idx)

            if match_to < right:
                # 在right之前, 一定没有到达字符串边界
                self.z_table[cur_idx] = self.z_table[offset]
            else:
                # 超过right边界, 从right开始匹配(包括超过边界情况)
                # assert match_to >= right
                matched_cnt = right - cur_idx
                aug_matched_cnt = self._match_from(z_from=right, origin_from=right - cur_idx)
                self.z_table[cur_idx] = matched_cnt + aug_matched_cnt
                left = cur_idx
                if matched_cnt + aug_matched_cnt == pattern_len and cur_idx >= pattern_len:
                    return None, cur_idx

                right = right + aug_matched_cnt # 如果aug_matched_cnt > 0 则更新right, 否则计算出来还是原值

            cur_idx += 1

        return right, -1


def main():
    print("start main")

    s = Solution()
    r = s.strStr('', '')
    r = s.strStr('basdaf', 'sd')
    # r = s.strStr('asdf', 'df')
    print(r)


if __name__ == "__main__":
    main()
